1. Technical Field
The invention relates to computer data structures. More particularly, the invention relates to an enhanced stack unwinding facility, for example, for use with such computer data structures as runtime exception handlers.
2. Description of the Prior Art
Many computer languages provide a procedure (referred to as an exception handler) that is executed when an unusual event (referred to as a runtime exception) occurs during program execution. The exception handler may print an error message or alter a global data structure. The exception handler may also execute a non-local "go to" instruction to allow the program flow to return an outer level procedure, such that the program may recover quickly from the error.
Each ordinary procedure in a program may provide a different exception handler. If a particular procedure fails to provide an exception handler, then that procedure inherits an exception handler from the procedure that called the failed procedure. The calling procedure may have in turn inherited its exception handler from a procedure by which it was called, and so on.
A particular procedure may be called from many different places in a program and may therefore use any number of different exception handlers.
Further, an exception may occur at a point in a program where a highly optimizing compiler has allocated variables to registers in a manner that is not discernible or known by the exception handler.
Stack unwinding refers to the process of procedure track-back and context restoration, for example in response to an unusual event during execution of a program, such as an exception. See, for example, HP 3000/930 and HP 9000/840 Computers--Procedure Calling Conventions Manual, Hewlett-Packard Corporation, Ch. 7 (January 1991).
Stack unwinding depends upon the ability of the system to determine the state of the stack for any given instruction, and whether that instruction is part of a procedure entry or exit sequence. When an exception occurs and the current procedure has not specified an exception handler, the runtime system must unwind the procedure call stack. That is, the runtime system must methodically undo the effect of each procedure call, e.g. by restoring registers and popping stack frames, until a desired outer-level procedure is reached that provides an exception handler. Thus, the runtime system must know the size of each frame and which registers were saved, e.g. because an optimizing compiler saves as few registers as possible in each frame.
The procedure calling mechanism for a complex instruction set computer (CISC) provides a frame pointer which, together with the stack pointer, indicates the frame size. Often, the stack frame contains a bit mask that indicates which registers were saved. Sometimes, another bit mask or pointer indicates exception handlers. In this case, stack unwinding and exception handling are relatively straightforward, although every procedure call incurs the computational expense of updating the frame pointer and manipulating the bit masks, even if the program never encounters an exception.
Similar issues arise in reduced instruction set computers (RISC). See, for example, M. Himelstein, S. Correll, K. Enderby, A RISC Approach to Runtime Exceptions, Summer USENIX '88, pp. 239-249 (June 1988). More significantly, RISC computers typically must infer the mechanism by which the program arrived at the point at which the exception is encountered. The state of the art provides a binary search mechanism that is computationally expensive.
It would be advantageous to provide a compact, easily implemented stack unwinding mechanism that does not significantly affect processor speed, e.g. that provides fast exception handling.